COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Discussion of equality for lisp book
C00005 ENDMK
C⊗;
Discussion of equality for lisp book

The following discussion of equality should be included in chapter I
somewhere.

	The way %2cons%1 is programmed causes complications with
equality.  Pure LISP programs would be easiest to write and the mathematics
would be simplest if we could forget about %2eq%1 and use only
%2equal%1 which would then correspond to logical equality of
S-expressions.  When efficiency isn't important, this can be done.
However, the program for %2equal%1 must recur through both S-expressions,
while %2eq%1 need only compare the addresses of the lead words of the
list structures that represent them.

	The problem is that the program for %2cons%1 takes a word
from the %2free storage list%1 and puts %2x%1 and %2y%1 into its
qa and qd parts without checking whether a word with these qa and
qd parts already exists in memory.  If %2cons%1 searched memory and
returned a pointer to the existing word if there was one, then %2eq%1
could be used for %2equal%↔1, and also memory would be economized.
This search would be impractically lengthy if done straightforwardly,
but schemes based on hashing have been devised that are practical.
However, hash %2cons%1 is incompatible with some of the programs that
modify list structure.

	Since non-numerical atoms are guaranteed unique (by one or
another hashing scheme) %2eq%1 may be used when at least one of
the arguments is sure to be an atom.  Moreover, if %2eq%1 asserts
that two non-atomic list structures are equal, they surely are.
In some other cases, the history of the computation assures us
that two S-expressions are equal only if they are represented
by the same list structure, and %2eq%1 can again be used.